/**
 * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
 * 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空
 * 子字符串：
 * s = s1 + s2 + ... + sn
 * t = t1 + t2 + ... + tm
 * |n - m| <= 1
 * 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
 * 注意：a + b 意味着字符串 a 和 b 连接。
 * 
 * 0 <= s1.length, s2.length <= 100
 * 0 <= s3.length <= 200
 * s1、s2、和 s3 都由小写英文字母组成
 */

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(),m = s2.size();
        if(n + m != s3.size()){
            return false;
        }
        vector dp(n + 1,vector<int>(m + 1));
        dp[0][0] = true;
        for(int j = 0;j < m;j++){
            dp[0][j + 1] = s2[j] == s3[j] && dp[0][j];
        }
        for(int i = 0;i < n;i++){
            dp[i + 1][0] = s1[i] == s3[i] && dp[i][0];
            for(int j = 0;j < m;j++){
                dp[i + 1][j + 1] = s1[i] == s3[i + j + 1] && dp[i][j + 1] || s2[j] == s3[i + j + 1] && dp[i + 1][j];
            }
        }
        return dp[n][m];
    }
};